package org.regotto.basics.sort;

import org.regotto.common.Utils;

public class HeapSort {

    static int[] h = new int[]{0, 3, 1, 2, 4};
    static int size = h.length - 1;

    // 构成小顶堆
    static void down(int u) {
        int t = u;
        if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
        if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
        if (u != t) {
            Utils.swap(h, t, u);
            down(t);
        }
    }

    public static void main(String[] args) {
        for (int i = size / 2; i > 0; i--)
            down(i);
        for (int i = 4; i > 0; i--) {
            System.out.println(h[1]);
            h[1] = h[size--];
            down(1);
        }
    }

}
